1. Field of the Invention
This invention relates to an associative memory having separately associable zones, with a linearly addressable main memory for the input and read-out of data composed of an associative component and a non-associative component, with a comparator device serving to compare the read-out association words with a search word, with a device containing address converters, serving to derive the addresses from the association and search words or from the higher-value bits of these words, and with an extension counter whose count influences the derivation of the addresses and is increased by one when an initially addressed storage position proves occupied.
2. Description of the Prior Art
The German published application 2,319,468 discloses a storage device having a plurality of storage banks which, in turn, comprise a plurality of storage positions and which are each classified into an associative portion which can be addressed by a part (prefix) of the association and search word, and into a non-associative portion which serves to accommodate an assigned word. Each storage bank is assigned address converters for deriving the addresses from the association and search word in a manner which differs from storage bank to storage bank, with pseudo-statistical distribution, in such a manner that the prefix lines which connect to one another the storage positions, capable of being addressed by specific prefixes, of adjacent storage banks, form irregular lines. All of the entries on one prefix line are read out simultaneously.
A random accumulation of association words having the same prefix can give rise to this situation in which the storage positions available along a prefix line are not sufficient for the entry of the words. Therefore, the storage device is provided with an extension counter whose relevant count co-determines the formation of the addresses and is increased by one whenever a new entry of a word having a specific prefix is to be made and all of the storage positions along the relevant prefix line are already in use. Thus, the extension counter serves to provide additional addressing planes which can accommodate extensions of prefix lines.
The possibility of surveying the state of seizure along a prefix line considerably simplifies the allocation of free storage positions for new entries. Thus, on average, only two search cycles are required for the relocation of free storage positions when the memory is approximately 95% or more full. In the event of a reduction in the number of storage banks, however, the conditions rapidly deteriorate. The state of seizure becomes increasingly difficult to survey and, on account of the reduction in length of the prefix lines, the selection between equivalent storage positions becomes poor.
However, by means of the application of suitable measures, it is possible to advantageously also employ a linearly addressable main memory divided into pages and rows and possessing only one storage bank as an associative store. In this case, it is of considerable importance to provide a book-keeping memory in which the rows (words) are assigned to the pages of the main memory and the bit positions within the words are assigned to the rows within the pages of the main memory. By setting markings in the bit positions of the book-keeping memory for the rows of the main memory which are in use, it is possible to rapidly survey the particular state of seizure of the main memory.
The addresses for the pages and rows of the main memory are obtained from the association and search words, or from parts of these words. The bit positions employed for the address formation of the association and search words are referred to as prefix, irrespectively of whether the prefix comprises only the higher-value bit positions of these words or the entire words. There are various possibilities of deriving the page and row addresses of the main memory, these resulting in partially differing storage modes for new entries of association words. A common feature of all exemplary embodiments which will be discussed in detail hereinbelow is a page address converter which consists of a logic linking network or a small read only memory (ROM). At its output, the latter emits, in parallel, as many bits as are present at its input. It is generally possible to dispense with a special row address converter.
For many applications it is advantageous to employ a prefix comprising more bits than are necessary for addressing. The prefix is then compressed by logic linking networks by read-only memory.
As, generally speaking, the number of storage positions in the main memory is less than the number of possible combinations of all of the bit positions of the association words, independently of the special nature of the address information, a plurality of association words always lead to the same addresses. Therefore, it will frequently occur that a storage position in the main memory selected by the original page and row address proves to be already in use when a new association word is to be stored. However, since the state of seizure of the main memory is portrayed in the book-keeping memory, it is possible to allocate an equivalent storage position for the awaiting new entry, both easily and rapidly. For this purpose, an extension counter is provided, the relevant count of which co-determines the formation of the page addresses and, commencing from 0, is increased by one counter unit whenever the previously addressed storage position is already in use. In this manner, a chain of association words is constructed, which words are similar to one another and which all initially lead to the same addresses of the main memory.
In the formation of change of this kind, it is advantageous to control the translation function of the page address converter by a few (three or four, for example) low-value bits of the relevant count of the extension counter. The higher-value bits from the extension counter are added to the bits at the outut of the page address converter without increasing the number of digits (positions). The result of the addition represents the page address.
Memory contents often consists of a plurality of independent data groups, where the data within the individual groups are organizationally interrelated. Such data groups can, for example, be translation tables, decision tables, programs, program components, and the like. In the following discussion such groups will be referred to as independent tables. The processing of tables of this type in large associative memories comprising a plurality of independent tables is, in many cases, considerably simplified if the individual tables are allocated separately associable storage cells. Here, reference will only be made to the sorting of table contents in the case of which the entire memory would otherwise have to be systematically searched through.